package leetcode;

import java.util.*;

public class LeetCodeMain106 {
    public int maxSubArray(int[] nums) {
        if (nums.length==1){
            return nums[0];
        }
        int sum=Integer.MIN_VALUE;
        int min=0;
        for (int i = 0; i < nums.length; i++) {
            min+=nums[i];
            if (min>sum){
                sum=min;
            }
            if (min<0){
                min=0;
            }
        }
        return sum;
    }
    public char firstUniqChar(String s) {
        Map<Character, Integer> frequency = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < s.length(); ++i) {
            if (frequency.get(s.charAt(i)) == 1) {
                return s.charAt(i);
            }
        }
        return ' ';
    }
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k==0||arr.length==0||arr==null||arr.length<k){
            return new int[1];
        }
        PriorityQueue<Integer> queue=new PriorityQueue<>((o1, o2) -> o2-o1);
        for (int i = 0; i < arr.length; i++) {
            if (i<=k-1){
                queue.offer(arr[i]);
            }else {
                if (arr[i]<queue.peek()){
                    queue.poll();
                    queue.offer(arr[i]);
                }
            }
        }
        int[] nums=new int[k];
        for (int i = 0; i < k; i++) {
            nums[i]=queue.poll();
        }
        return nums;
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list=new LinkedList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        if (root!=null){
            queue.offer(root);
        }
        int count=1;
        while (!queue.isEmpty()){
            Deque<Integer> res = new LinkedList<Integer>();
            int size=queue.size();
            while (size-->0){
                TreeNode n=queue.poll();
                if (count==1){
                    res.offerLast(n.val);
                }else {
                    res.offerFirst(n.val);
                }
                if (n.left!=null){
                    queue.offer(n.left);
                }
                if (n.right!=null){
                    queue.offer(n.right);
                }
            }
            if (!res.isEmpty()){
                list.add(new LinkedList<>(res));
            }count=count*-1;
        }
        return list;
    }
    public int[] spiralOrder(int[][] matrix) {
        if (matrix==null||matrix.length==0||matrix[0]==null||matrix[0].length==0){
            return new int[0];
        }
        int x=matrix.length-1;
        int y=matrix[0].length-1;

        int i=0;
        int j=0;
        int count=0;
        int[] arr=new int[(x+1)*(y+1)];
        while (i<=x&&j<=y){
            for (int t = j; t <= y; t++) {
                arr[count++]=matrix[i][t];
            }
            i++;
            if (i>x){
                break;
            }
            for (int t = i; t <= x; t++) {
                arr[count++]=matrix[t][y];
            }
            y--;
            if (j>y){
                break;
            }
            for (int t = y; t >= j; t--) {
                arr[count++]=matrix[x][t];
            }
            x--;
            if (i>x){
                break;
            }
            for (int t = x; t >= i; t--) {
                arr[count++]=matrix[t][j];
            }
            j++;
            if (j>y){
                break;
            }
        }
        return arr;
    }
}
